package classic150

import "sort"

// 88. 合并两个有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
	copy(nums1[m:], nums2)
	sort.Ints(nums1)
}

// 27. 移除元素
func removeElement(nums []int, val int) int {
	s, f := 0, 0
	for ; f < len(nums); f++ {
		if val != nums[f] {
			nums[s] = nums[f]
			s++
		}
	}
	return s
}

// 49. 字母异位词分组
func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}

	for _, str := range strs {
		s := []byte(str)
		sort.Slice(s, func(i, j int) bool {return s[i] < s[j]})
		sortStr := string(s)
		mp[sortStr] = append(mp[sortStr], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

// 128 最长连续序列
func longestConsecutive(nums []int) int {
	mmap := map[int]bool{}
	
	for _, num := range nums {
		mmap[num] = true
	}

	ans := 0
	
	for _, num := range nums {
		if !mmap[num - 1] {
			curr := num
			currL := 1
			for mmap[curr + 1] {
				curr++
				currL++
			}
			if ans < currL {
				ans = currL
			}
		}
	}

	return ans
}


// 283. 移动零
func moveZeroes(nums []int) {
	i, j, n := 0, 0, len(nums)
	for j < n {
		if nums[j] != 0 {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
		j++
	}
}

// 11。 盛最多水的容器
func maxArea(height []int) int {
	left, right := 0, len(height) - 1
	ans := 0
	for left < right {
		area := min(height[left], height[right]) * (right - left)
		ans = max(ans, area)
		if height[left] <= height[right] {
			left++
		}else {
			right--
		}
	}
	return ans
}

// 15. 三数之和
func threeSum(nums []int) [][]int {
	ans := [][]int{}
	n := len(nums)
	sort.Ints(nums)
	for i, x := range nums[:n-2] {
		if i > 0 && x == nums[i - 1] {
			continue
		}
		if x + nums[i + 1] + nums[i + 2] > 0 {
			break
		}
		if x + nums[n - 2] + nums[n - 1] < 0 {
			continue
		}
		j, k := i + 1, n - 1
		for j < k {
			s := x + nums[j] + nums[k]
			if s > 0 {
				k--
			}else if s < 0 {
				j++
			}else {
				ans = append(ans, []int{x, nums[j], nums[k]})
				for j++; j < k && nums[j] == nums[j -1]; j++ {}
				for k--; j < k && nums[k] == nums[k + 1]; k-- {}
			}
		}
	}
	return ans
}

// 42.接雨水
func trap(height []int) int {
	ans := 0 
	stack := []int{}
	for i, h := range height {
		// 如果此时遍历的元素大于栈顶元素，第一个是top，第二个是left，计算接雨水的面积，同时将top出栈
		for len(stack) > 0 && h > height[stack[len(stack) - 1]] {
			top := stack[len(stack) - 1]
			stack = stack[:len(stack) - 1]
			if len(stack) == 0 {
				break
			}
			left := stack[len(stack) - 1]
			curWidth := i - left - 1
			curHeight := min(height[left], h) - height[top]
			ans += curWidth * curHeight
		}
		stack = append(stack, i)
	}
	return ans
}

// 3.无重复字符的最长子串
// func lengthOfLongestSubstring(s string) int {
	
// }
